1. Field of Invention
The present invention relates generally to the field of internetworking. More specifically, the present invention is related to controlling traffic distribution between the links connecting an autonomous system to other autonomous systems.
2. Discussion of Relevant Art
An internetwork is a collection of individual, typically heterogenous, networks which are connected by internetworking devices, such as routers, to function as a single network. In these internetworks, such as the Internet, routing is the act of moving information, usually in the form of packets, from a source host to a destination host across the internetwork. In order to enable the routing of the information across the internetwork, a network layer (layer 3 of the OSI reference model) protocol is utilized to provide addressing information and some control information. The most ubiquitous network layer protocol in use today is the Internet Protocol (IP), which provides protocol addresses (in human readable form) in a manner termed dotted decimal notation (e.g. 10.1.1.1).
To route information from a source with one network layer protocol address to a destination device with a different network layer address, routers perform two activities. One of the activities is determining optimal routing paths in the internetwork and maintaining routing tables of these paths, while the other is the actual transport of the packets through the internetwork.
The actual transport of the packets across the internetwork is typically termed switching. For switching, a router typically receives a packet addressed to the routers physical address (Media Access Control (MAC)-layer address). This packet contains the network layer address of the destination host. The router then utilizes its routing table to determine if it knows how to forward this packet or not. If the router does not know how to forward the packet, the packet is dropped. On the other hand, if the router does know how to forward the packet, it changes the physical address to the physical address of the next device to receive the packet in order to get the packet to the destination. At times this next device is the destination host itself. When the next device is not the destination host, the next device is usually another router. This next router then receives the packet and performs the same switching process on the packet. Therefore, as the packet is propagated through the internetwork towards its destination host, the physical address of the packet changes, while the network layer address remains the same.
In order to determine how to forward a packet, routers maintain routing tables. Routing algorithms generate the routing tables maintained by the router using information received from other logically or physically connected routers concerning the networks that are reachable through those connected routers. Typically, these routing algorithms take the information received from the other routers and fill routing tables with information such as destination/next hop information. This destination/next hop information tells a router that a destination network address can be reached by sending the packet to a particular router as the “next hop” of the packets movement through the internetwork to its destination host. By checking a destination network layer address of a received packet for an associated next hop in the routing table, a router determines how to forward the packet.
As described, to build the routing tables, a router receives information from other connected routers concerning the networks reachable by those other routers. In order to communicate this information, routers utilize routing protocols. One such protocol is the Border Gateway Protocol (BGP). BGP is defined in Request For Comment (RFC) 1771, available at any of the RFC archives on the World Wide Web, such as BGP provides loop-free interdomain routing between autonomous systems (AS). An AS is normally defined in the art as a set of routers that operate under the same administration. For the Internet, ASs normally comprise Internet Service Providers (ISP) or other large organizational entities, such as universities, government organizations and large corporate networks. Peer border routers located on the boundaries of each AS exchange information pertaining to the reachability of blocks of IP addresses for transit networks and networks that originate from that AS.
An illustration of this is provided in FIG. 1. AS 100's border router 100 connects it to AS 200 and AS 300 via their respective border routers 104 and 102. AS 200's border router 104 additionally connects it to AS 400 via AS 400's border router 108. Likewise, AS 300's border router 102 connects it to AS 500 via AS 500's border router 106. AS 400 and AS 500 are also connected to each other via their respective border routers 108 and 106. Each of the connected border routers communicates reachability information to its peer routers utilizing BGP. Utilizing BGP messages, each of these border routers sends reachability information to its peers concerning a block of IP addresses, or prefixes, which it is capable of reaching. This reachability information is propagated throughout the internetwork and as it is propagated, each router along the path pre-pends its unique AS number to the BGP message. The list of pre-pended AS numbers constitutes the AS path of the route and, along with the prefix, designates a transit route through the network for a destination network layer address.
For instance, border router 100 determines that it is able to reach the block of network layer addresses 136.128.x.x. Border router 100 sends this information in a BGP message to its peers, border routers 104 and 102, along with other metrics concerning the respective links between border router 100 and border routers 104 and 102. This message includes AS 100's AS number. Border router 104 receives this message, stores this information and sends its own message to border router 108 indicating that the block of network layer addresses 216.128.x.x can be reached through it. When border router 104 sends this message, it pre-pends its AS number to the AS 100's number, so that the message contains AS 100's number and AS 200's number. In the same manner, border routers 108 and 102 propagate the reachability information throughout the network to their peers.
It is instructive to note that many times a router receives information about multiple routes to a particular destination. BGP on each border router uses the AS path to construct a loop free map of ASs and determines an optimal path from the multiple paths based, at least in part, on the number of AS's that must be crossed to reach the destination, also determined from the AS path.
For instance, referring again to FIG. 1, AS 500 is likely to determine that a packet destined for an IP address in the block 136.12.x.x is optimally routed to router 102 as its next hop. This is because the route using router 102 will traverse less ASs to reach its destination than the route, which utilizes router 108.
As the optimal routes are based upon network topology, once the router announces itself to its peers, incoming traffic distribution among the multiple links from its peers cannot be controlled by BGP. For example, BGP cannot control the distribution of incoming traffic to AS 100 between link 110 and link 112. In addition, BGP is limited in its knowledge about congestion and network performance over these multiple links At times an AS, particularly an ISP, may want to be able to control the link utilized for incoming traffic to a destination address based upon parameters of the links such as congestion, load or capacity. For instance, an ISP may want to have incoming traffic for preferred customers, e.g. those who pay for the service, come over a link that has the least congestion and load so as to provide faster data communications for that customer. Or an ISP may simply wish to provide optimal load balancing of its links so that all customers receive the optimal transmission rates.
The current prior art solution to control the links that incoming traffic for a particular destination arrives through is to manually separate the internal network into blocks of IP addresses (CIDR blocks), and statically announce these subnets differently toward the peer routers. This, however, is an unsatisfactory solution as it requires human resources and is generally not very accurate. Furthermore, this method is unsatisfactory as traffic is unable to be dynamically reshaped based upon current capacity, congestion, loading or when the health of any part of the internetwork becomes unstable.